import java.util.ArrayList;
import java.util.List;

class Solution4 {
    StringBuffer path;
    List<String> ret;
    // 数字和字母的映射
    String[] digitsMap = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) {
        path = new StringBuffer("");
        ret = new ArrayList<>();
        if (digits.length() == 0) {
            return ret;
        }
        dfs(digits, 0);
        return ret;
    }

    public void dfs(String digits, int pos) {
        if (pos == digits.length()) {
            ret.add(path.toString());
            return;
        }
        String tmp = digitsMap[digits.charAt(pos) - '0'];
        for (int i = 0; i < tmp.length(); i++) {
            path.append(tmp.charAt(i));
            dfs(digits, pos + 1);// 去下一个位置(pos+1)
            // 回溯
            path.deleteCharAt(path.length() - 1);
        }
    }
}